package com.lfx.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 李逢喜
 * create 2021/7/15
 */
public class BinaryTree {
    TreeNode root;



    public  void insertNode(int data){
        root=insert(root,data);
    }


    private TreeNode insert(TreeNode node, int data) {
        //父级节点
        if (node==null)return  new TreeNode(data);

        //二叉查树原则，左子树小于父级节点，右子树大于父级点
        if(data<node.data){//插入左边
            node.leftChild=insert(node.leftChild,data);
        }else if(data>node.data){
            node.rightChild=insert(node.rightChild,data);
        }else
            node.data=data;

        return node;

    }


    /**
     * 前序遍历
     * @param node
     */
    public  void preOrderTraveral(TreeNode node){
        if(node==null)
            return;
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }



    /**
     * 中序遍历
     * @param node
     */
    public  void inOrderTraveral(TreeNode node){
        if(node==null)
            return;
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }



    /**
     * 中序遍历
     * @param node
     */
    public  void postOrderTraveral(TreeNode node){
        if(node==null)
            return;
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public void levelTraver(TreeNode root){
        Queue<TreeNode> treeNodes=new LinkedList<TreeNode>();
        treeNodes.offer(root);
        while (!treeNodes.isEmpty()){
            TreeNode node = treeNodes.poll();
            System.out.println(node.data);
            if(node.leftChild!=null)
                treeNodes.offer(node.leftChild) ;
             if (node.rightChild!=null)
                treeNodes.offer(node.rightChild);
        }

    }


    

    public static void main(String[] args) {
        BinaryTree btt=new BinaryTree();
        btt.insertNode(10);
        btt.insertNode(8);
        btt.insertNode(11);
        btt.insertNode(7);
        btt.insertNode(9);
        btt.insertNode(12);

        btt.preOrderTraveral(btt.root);
        System.out.println("========================");
        btt.inOrderTraveral(btt.root);

        System.out.println("========================");
        btt.postOrderTraveral(btt.root);
        System.out.println("========================");
        btt.levelTraver(btt.root);
    }
}
